Many cryptographic schemes require the generation of a (random) prime each time it is used. Examples are signature schemes, group signature schemes, or credential systems, such as the so-called Cramer-Shoup signature scheme by R. Cramer and V. Shoup “Signature schemes based on the strong RSA assumption.” In Proc. 6th ACM Conference on Computer and Communications Security, pages 46-52. ACM press, November 1999, or the credential system by J. Camenisch and A. Lysyanskaya in their article “Efficient non-transferable anonymous multi-show credential system with optional anonymity revocation.” In B. Pfitzmann, editor, Advances in Cryptology—EUROCRYPT 2001, volume 2045 of LNCS, pages 93-118, Springer Verlag, 2001. The security of all these schemes is based on the so-called strong RSA assumption. More precisely, their security proofs require that each signatures or credentials is computed using a unique prime, i.e., the computation of each signature or credential involves computing an e-th root where e is said unique prime. The e is also referred to as unique exponent in the following.
Unfortunately, the generation of primes is computationally expensive, especially if they need to be large. Because of this, the generation of signatures or credentials in the above mentioned schemes becomes computationally involved.
For the generation of primes one could in principle each time choose any integer as unique exponent, as long as it possesses a prime factor that does not appear in any unique exponent that was used before. This would require to store all exponents used so far and test the newly chosen exponent against these numbers; which, however, is very inefficient.
From the above it follows that there is still a need in the art that the generation of a signature is simplified for these schemes. Usually, a new prime is necessary each time a signature is generated, this is rather inefficient. Therefore, it is advantageous to provide cryptographic keys and signature values more efficiently. Each signature value should be verifiable.
Glossary
The following are informal definitions to aid in the understanding of the description.                Credential: In the present context is understood under the term credential, a subset of access permissions (developed with the use of media-independent data) attesting to, or establishing, the identity of an entity, such as a birth certificate, driver's license, mother's maiden name, social security number, fingerprint, voice print, or other biometric parameter(s). Moreover, the credential comprises information, passed from one entity to another, used to establish the sending entity's access rights. The term certificate is understood as a particular credential stating that a certain public key belongs to a certain entity or user.        Signature: A digital signature consists of one or more values that relate a message to a public key. A signature can only be produced using the secret key corresponding to the public key.        
The following signs relate to the terms indicated beside and are used within the description.
A, B, C, Dcomputer nodesp, qprimesnproduct of p and qsksecret key being derived from p and qAfirst random limitvinterval widthsA, vexponent-interval descriptionIexponent intervalu, lsecurity parametereexponent valuee′random primemmessagex′verification valueHhash functionQRnelements having a square root modulo ny′, h, xelements of QRnycomputed signature root valuey, y′, esignature valueh, xpublic valuesn, h, x, e′, Ipublic key valuepkpublic key comprising public key value (n, h, x, e′, I) andexponent-interval description (A, v)urandom bit-numbers